//基于邻接矩阵的深度优先算法

//先构建邻接矩阵结构
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status; /*Status 是函数的类型，返回函数结果状态*/
typedef int Boolean; /*Boolean 是布尔类型，其值是TRUE或FALSE*/

typedef char VertexType; /*顶点类型由用户定义*/
typedef int EdgeType; /*边上的权值类型由用户定义*/

#define MAXSIZE 9   /*储存空间初始分配量*/
#define MAXEDGE  15
#define MAXVEX 9
#define INFINITYC 65535

typedef struct 
{
    VertexType vexs[MAXVEX]; /*顶点表*/
    EdgeType arc[MAXVEX][MAXVEX]; /*邻接矩阵，可以看作边表*/
    int numVertices,numEdges;  /*图中当前的顶点数和边数*/
}MGraph;

/*构建一个邻接矩阵*/
void CreateMGraph(MGraph *G)
{
    int i,j;

    //1.确定图的顶点数
    G->numEdges=15;
    G->numVertices=9;

    //2.读入顶点信息，建立顶点表
    for(i=0;i<9;i++)
    {
        G->vexs[i]='A'+i;
    }

    //3.初始化图中的边表
    for(i=0;i<G->numVertices;i++)
    {
        for(j=0;j<G->numVertices;j++)
        {
            G->arc[i][j]=0;
        }
    }

    //4.将图中的连接信息输入到边表中
    //保证 j 比 i 大（即填充矩阵的上三角部分）
    G->arc[0][1]=1;
    G->arc[0][5]=1;

    G->arc[1][2]=1;
    G->arc[1][8]=1;
    G->arc[1][6]=1;

    G->arc[2][3]=1;
    G->arc[2][8]=1;

    G->arc[3][4]=1;
    G->arc[3][7]=1;
    G->arc[3][6]=1;
    G->arc[3][8]=1;

    G->arc[4][5]=1;
    G->arc[4][7]=1;

    G->arc[5][6]=1;

    G->arc[6][7]=1;

    //5.无向图是对称矩阵
    for(i=0;i<G->numVertices;i++)
    {
        for(j=i;j<G->numVertices;j++)
        {
            G->arc[j][i]=G->arc[i][j];
        }
    }
}

/*3.DFS 遍历*/
Boolean visited[MAXVEX]; //标志访问的数组
//1.标识顶点是否被标记过
//2.选择从某一个顶点开始（注意非连通图的情况）
//3.进入递归，打印 i 点信息，标记;
//4.[i][j]是否等于1

void DFS(MGraph &G,int i)
{
    //1.标记起点并输出
    visited[i]=TRUE;
    printf("%c",G.vexs[i]);

    //2.0~numVertices
    for(int j=0;j<G.numVertices;j++)
    {
        if(G.arc[i][j]==1&&!visited[j])
        {
            DFS(G,j);
        }
    }
}

void DFSTraverse(MGraph G)
{
    //1.初始化visited数组
    for(int i=0;i<G.numVertices;i++)
    {
        visited[i]=FALSE;
    }

    //2.某一个顶点
    for(int i=0;i<G.numVertices;i++)
    {
        if(!visited[i])
        {
            DFS(G,i);
        }
    }
}


void MGraph_DFS()
{
    printf("邻接矩阵的深度优先遍历！\n");
    MGraph G;
    CreateMGraph(&G);
    DFSTraverse(G);
    printf("\n");
    //输出与图片所示一致
}


/*邻接表结构*/
typedef struct EdgeNode /*边表结构点*/
{
    int adjvex; /*邻接点域，储存该顶点对应的下标*/
    int weight;  /*用于储存权值，对于非网图可以不要*/
    struct EdgeNode *next; /*链域，指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode /*顶点表结点*/
{
    int in; /*顶点入度*/
    char data; /*顶点域，储存顶点信息*/
    EdgeNode *firstedge; /*边表头指针*/
}VertexNode,AdjList[MAXVEX];

typedef struct 
{
    AdjList adjList;
    int numVertices,numEdges;
}graphAdjList,*GraphAdjList;

//利用邻接矩阵构建邻接表
void CreateALGraph(MGraph &G,GraphAdjList &GL)
{
    //1.创建邻接表，并且设计邻接表的定点数以及弧数
    GL=(GraphAdjList)malloc(sizeof(graphAdjList));
    GL->numVertices=G.numVertices;
    GL->numEdges=G.numEdges;

    //2.从邻接矩阵中将顶点信息输入
    for(int i=0;i<G.numVertices;i++)
    {
        //顶点入度为0
        GL->adjList[i].in=0;
        //顶点信息
        GL->adjList[i].data=G.vexs[i];
        //顶点边表头指针置空
        GL->adjList[i].firstedge=NULL;
    }

    //3.建立边表
    EdgeNode* e;
    for(int i=0;i<G.numVertices;i++)
    {
        for(int j=0;j<G.numVertices;j++)
        {
            if(G.arc[i][j]==1)
            {
                //创建边表中的邻接结点 i->j
                e=(EdgeNode*)malloc(sizeof(EdgeNode));
                //邻接序号为 j
                e->adjvex=j;
                //将当前结点的next指向adjList[i]的顶点边表上
                //头插法
                e->next=GL->adjList[i].firstedge;
                GL->adjList[i].firstedge=e;
                //顶点 j 上的入度++
                GL->adjList[j].in++;
            }
        }
    }
}

//邻接表的深度优先递归算法
//Boolean visited[MAXSIZE];

void DFS(GraphAdjList &GL,int i)
{
    //1.标记已经被访问
    EdgeNode *p;
    visited[i]=TRUE;

    //2.打印顶点
    printf("%c",GL->adjList[i].data);
    p=GL->adjList[i].firstedge;

    //3.递归
    //如果下一个顶点未被访问，则继续递归
    //否则，则 p 移动到下下个顶点
    while(p)
    {
        if(!visited[p->adjvex])
        {
            DFS(GL,p->adjvex);
        }
        p=p->next;
    }
}

void DFSTraverse(GraphAdjList &GL)
{
    //1.将visited数组默认设置为FALSE
    for(int i=0;i<GL->numVertices;i++)
    {
        visited[i]=FALSE;
    }

    //2.选择一个顶点开始DFS遍历
    for(int i=0;i<GL->numVertices;i++)
    {
        //对未访问的顶点调用DFS,若是连通图则只会调用一次
        if(!visited[i])
        {
            if(!visited[i])
            {
                DFS(GL,i);
            }
        }
    }
}

//基于邻接表的深度优先遍历
void ALGraph_DFS()
{
    printf("邻接表的深度优先遍历！\n");
    MGraph G;
    GraphAdjList GL;
    CreateMGraph(&G);
    CreateALGraph(G,GL);

    DFSTraverse(GL);
    printf("\n");
}
int main()
{
    MGraph_DFS();
    ALGraph_DFS();
    return 0;
}
